package com.gitee.feizns.explore.data_structure.sort;

import java.util.Arrays;

/**
 * @author feizns
 * @since 2019/11/19
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] arr = new int[]{ 5, 4, 3, 2, 1 };
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            siftUp(arr, i);
        }

        for (int i = 1; i < arr.length; i++) {
            swap(arr, 0, arr.length - i);
            siftDown(arr, arr.length - i, 0);
        }
    }

    private static void siftUp(int[] arr, int ind) {
        int p;
        while ((p = parent(ind)) >= 0 && arr[ind] > arr[p] ) {
            swap(arr, ind, p);
            ind = p;
        }
    }

    private static void siftDown(int[] arr, int len, int ind) {
        while ( true ) {
            int l = left(ind);
            int r = right(ind);
            int maxChild = -1;
            if ( l < len )
                maxChild = r < len && arr[r] > arr[l] ? r : l;

            if ( maxChild != -1 && arr[maxChild] > arr[ind] ) {
                swap(arr, ind, maxChild);
                ind = maxChild;
            } else {
                break;
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private static int parent(int i) {
        if ( i == 1 )
            return 0;
        else if ( i > 1 )
            return (i - 1) / 2;
        return -1;
    }

    private static int left(int i) {
        return i * 2 + 1;
    }

    private static int right(int i) {
        return i * 2 + 2;
    }

}
